The present invention relates to a system and method for facilitating access to and use of geographic data used with a navigation application program that provides navigating features and functions to a user, and more particularly, the present invention relates to a method and system for organization, storage and retrieval of geographic data that facilitates use of the geographic data for various navigating functions provided by a navigation application program.
Computer-based navigation application programs are available that provide users with various navigating functions and features. For example, some navigation application programs are able to determine an optimum route to travel by roads between locations. Using input from a user, and optionally from equipment that can determine one's physical location (such as a GPS system), a navigation application program can examine various routes between two locations to determine an optimum route to travel from a starting location to a destination location in a geographic region. The navigation application program may then provide the user with information about the optimum route in the form of instructions that identify the maneuvers required to be taken by the user to travel from the starting location to the destination location. If the navigation system is located in an automobile, the instructions may take the form of audio instructions that are provided along the way as the user is traveling the route. Some navigation application programs are able to show detailed maps on computer displays outlining routes to destinations, the types of maneuvers to be taken at various locations along the routes, locations of certain types of features, and so on.
In order to provide these and other navigating functions, the navigation application program requires one or more detailed databases that include data which represent physical features in a geographic region. The detailed database may include data representing the roads and intersections in a geographic region and also may include information about the roads and intersections in a geographic region, such as turn restrictions at intersections, speed limits along the roads, the locations of stop signs, street names of the various roads, address ranges along the various roads, and so on.
Several of the navigation functions provided in a navigation system may require access to the geographic data spatially. One way this arises is that a function in a navigation application program requires finding a record, such as a data entity, in a geographic database given the physical location in the geographic region of the geographic feature represented by the data entity. The data entity may be a road segment record that represents a portion of a road in the geographic region and the function may require finding the road segment record based upon the physical location in the geographic region of the portion of the road represented by the road segment record. Another way spatial access arises is when a function in a navigation application program requires finding several or all of a type of data records located close to a location in the geographic region or within a defined area in the geographic region. For example, a function may require all road segment records encompassed within a rectangle defined by geographical coordinates (x, x+n) latitude and (y, y+m) longitude.
The map display function is a function of the type that may access geographic data spatially. The map display function may display a selected portion of the geographic region on a display screen. In order to generate such a map from a collection of database entities (or records) that represent portions of roadways in the geographic region, it is typically required to load into memory all of the road segment data entities corresponding to the portions of roadways in the selected portion of the geographic region. The data entities corresponding to the portions of roadways in the selected portion of the geographic region may need to be accessed from the data storage medium upon which the geographic database for the entire region is stored. If the road segment data entities corresponding to the selected portion of the geographic region which is desired to be displayed are located at various places on the storage medium on which the geographic database is stored, a large number of disk accesses might be required to obtain all the necessary records. This can result in relatively poor performance.
Another of the navigation functions that may be included in the navigation system is route calculation. This function provides a user of the system with an optimum route for traveling from one location in a geographic area to a destination location. In order to determine the optimal route, the route calculation function requires access to road segment data entities to determine certain data attributes, such as speed limits, turn restrictions, and so on, associated with the road segment data entities along the various possible routes between the starting location and the destination location. As with the map display function, mentioned above, the route calculation function requires access to road segment records spatially, i.e. based on the locations of the portions of the roadways in the geographic area to which the data entity records correspond. For example, as part of the route calculation procedure, when the route calculation function determines the optimum road to take from an intersection, it may access all the roads that lead from the intersection. Thus, all the road segment records that represent portions of roadways that meet at the intersection are accessed and examined. Like the map display function, the route calculation function requires that the road segment records be accessed by locations in the geographic area of the roadways to which they correspond.
Another function provided by navigation systems is maneuver generation. This function provides the user of the navigation system with instructions for traveling from one location to a destination location, based upon the optimum route calculated by the route calculation function. Given a list output from by the route calculation function that identifies the road segment records corresponding to portions of roadways for traveling from one location in the geographic region to a destination location in the geographic region, the maneuver generation function provides the user with a series of maneuver instructions. As part of the maneuver generation function, the names of the roads are found that correspond to the road segment records identified in the list calculated by the route calculation function. Depending on the way the information is stored in the geographic database, it may be necessary to access the road segment records based on the locations of the portions of roadways which they represent to identify the corresponding locations in the geographic database that includes the names of the roads in order to provide the maneuver instructions.
As demonstrated above, these functions in a navigation application program, and possibly other functions in navigation systems, require accessing data records spatially, i.e. based on the locations of the features in the geographic region to which the records correspond. Further, as suggested by the above examples, some functions in a navigation application program may require accessing a group of data records that correspond to features in a geographic area that are spaced together relatively closely in the geographic region.
Assuming that all the data records for a given entire geographic region cannot be loaded into memory at the same time due to limited memory resources of the navigation system in which the navigation application program is being run, it would be desirable to load into memory only those data that are needed. Since some of the navigation functions require accessing data spatially, it would be advantageous to provide a means to load data into memory based generally upon the physical geographic locations of the features which the data represent or upon the geographical proximity of the features which the data represent.